The problem can be found at the following link: Question Link
To check if a binary tree contains a duplicate subtree of size 2 or more. It does so by checking if there are any identical subtrees within the tree.
Here are the steps in my approach:
- The dupSub function does a level-order traversal of the binary tree using a queue to extract all the nodes.
- While traversing the tree, it identifies non-leaf nodes and stores them in the nodes vector.
- After collecting non-leaf nodes, it iterates through the nodes vector and compares each pair of nodes using the same function to check if they have the same structure and values. If a match is found, it returns true, indicating the presence of a duplicate subtree.
- If no duplicate subtree is found during the iteration, it returns false.
-
Time Complexity: The time complexity of this approach is
O(N)
, whereN
is the number of nodes in the binary tree. This is because we visit each node once to calculate its height and check the balance condition. -
Space Complexity: The space complexity is
O(H)
, whereH
is the height of the binary tree. In the worst case, the space complexity isO(N + H)
for a skewed tree, and in the best case, it isO(N)
for a balanced tree. This space is used for the recursive call stack.
bool same(Node * x, Node * y)
{
if((x == nullptr) ^ (y == nullptr))
return 0;
if((x == nullptr) and (y == nullptr))
return 1;
if(x -> data != y -> data)
return 0;
return same(x -> left, y -> left) and same(x -> right, y -> right);
}
class Solution {
public:
/*This function returns true if the tree contains
a duplicate subtree of size 2 or more else returns false*/
int dupSub(Node *root)
{
vector<Node *> nodes;
queue<Node *> q;
q.push(root);
while(!q.empty()){
Node * cur = q.front();
q.pop();
bool leaf = 1;
if(cur -> left != nullptr)
{
q.push(cur -> left);
leaf = 0;
}
if(cur -> right != nullptr)
{
q.push(cur -> right);
leaf = 0;
}
if(!leaf)
nodes.push_back(cur);
}
for(int i = 0; i < nodes.size(); i++)
{
for(int j = i + 1; j < nodes.size(); j++)
{
if(same(nodes[i], nodes[j]))
return 1;
}
}
return 0;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.